//
// Created by xili on 2024/8/29 20:20.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int distinctPrimeFactors(vector<int> &nums) {
        unordered_set<int> us;
        vector<int> zhi(getZhi(1000));
        for (auto &it: nums) {
            for (auto &item: zhi) {
                if (item >= it) {
                    break;
                }
                if (it % item == 0) {
                    us.insert(item);
                }
            }
        }
        return us.size();
    }

    vector<int> getZhi(int n) {
        vector<int> res(n + 1, 1);
        vector<int> ans;
        for (int i = 2; i <= n; i++) {
            if (res[i] == 1) {
                ans.push_back(i);
                for (int j = i * i; j <= n; j += i) {
                    res[j] = 0;
                }
            }
        }
        return ans;
    }
};